package com.jp.code.leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * 70
 * https://leetcode.cn/problems/climbing-stairs/
 */
public class ClimbStair {
    public static int climbStairs1(int n) {
        if (n <= 2) return n;
        int k1 = 1;
        int k2 = 2;
        for (int i = 3; i <= n; i++) {
            int t = k1 + k2;
            k1 = k2;
            k2 = t;
        }
        return k2;
    }


    static Map<Integer, Integer> map = new HashMap<>();

    public static int climbStairs2(int n) {
        if (n <= 2) return n;
        if (map.get(n) != null) {
            return map.get(n);
        } else {
            int result = climbStairs2(n - 1) + climbStairs2(n - 2);
            map.put(n, result);
            return result;
        }
    }

    public static void main(String[] args) {
        assert climbStairs1(1) == 1 : "不符合预期结果";
        assert climbStairs1(2) == 2 : "不符合预期结果";
        assert climbStairs1(3) == 3 : "不符合预期结果";
        assert climbStairs1(4) == 5 : "不符合预期结果";
        assert climbStairs1(5) == 8 : "不符合预期结果";
        System.out.println("OK");
    }

}
